﻿
#region Usings
using System.Collections.Generic;

#endregion

namespace LongNet.Util.Math
{
    /// <summary>
    /// Class that creates permutations (not implemented yet)
    /// </summary>
    public static class Permutation
    {
        #region Public Static Functions

        /// <summary>
        /// Finds all permutations of the items within the list
        /// </summary>
        /// <typeparam name="T">Object type in the list</typeparam>
        /// <param name="Input">Input list</param>
        /// <returns>The list of permutations</returns>
        public static List<List<T>> Permute<T>(List<T> Input)
        {
            List<T> Current=new List<T>();
            Current.AddRange(Input);
            List<List<T>> ReturnValue = new List<List<T>>();
            int Max = MathHelper.Factorial(Input.Count - 1);
            for (int x = 0; x < Input.Count; ++x)
            {
                int z = 0;
                while (z < Max)
                {
                    int y = Input.Count - 1;
                    while (y > 1)
                    {
                        T TempHolder = Current[y - 1];
                        Current[y - 1] = Current[y];
                        Current[y] = TempHolder;
                        --y;
                        List<T> TempList = new List<T>();
                        TempList.AddRange(Current);
                        ReturnValue.Add(TempList);
                        ++z;
                        if (z == Max)
                            break;
                    }
                }
                if (x + 1 != Input.Count)
                {
                    Current.Clear();
                    Current.AddRange(Input);
                    T TempHolder2 = Current[0];
                    Current[0] = Current[x + 1];
                    Current[x + 1] = TempHolder2;
                }
            }
            return ReturnValue;
        }

        #endregion
    }
}